/**
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 *
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 * 思路：原地哈希法
 * 除了打标记以外，我们还可以使用置换的方法，将给定的数组「恢复」成下面的形式：
 *
 * 如果数组中包含 x∈[1,N]，那么恢复后，数组的第 x - 1x−1 个元素为 x。
 *
 * 在恢复后，数组应当有 [1, 2, ..., N] 的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以题目中的示例二 [3, 4, -1, 1] 为例，恢复后的数组应当为 [1, -1, 3, 4]，我们就可以知道缺失的数为 22。
 *
 * 那么我们如何将数组进行恢复呢？我们可以对数组进行一次遍历，对于遍历到的数 x =nums[i]，如果 x∈[1,N]，我们就知道 x 应当出现在数组中的 x−1 的位置，因此交换 nums[i] 和nums[x−1]，这样 xx 就出现在了正确的位置。在完成交换后，新的 nums[i] 可能还在 [1, N][1,N] 的范围内，我们需要继续进行交换操作，直到 x∈[1,N]。
 *
 * 注意到上面的方法可能会陷入死循环。如果 nums[i] 恰好与 nums[x−1] 相等，那么就会无限交换下去。此时我们有 nums[i]=x=nums[x−1]，说明 x 已经出现在了正确的位置。因此我们可以跳出循环，开始遍历下一个数。
 *
 * 由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为 NN，整个方法的时间复杂度为 O(N)O(N)。
 *
 * 作者：LeetCode-Solution
 * 链接：https://leetcode.cn/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class FirstMissingPositive {
    public int firstMissingPositive(int[] nums) {
        int n=nums.length;
        for(int i=0;i<n;i++){
            while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){
                int tmp=nums[nums[i]-1];
                nums[nums[i]-1]=nums[i];
                nums[i]=tmp;
            }
        }
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return n+1;
    }
}